package medium.iterator;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * <a href="https://leetcode-cn.com/problems/flatten-nested-list-iterator">341. 扁平化嵌套列表迭代器</a>
 * 给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。
 * 列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。
 * 示例 1:
 *   输入: [[1,1],2,[1,1]]
 *   输出: [1,1,2,1,1]
 *   解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。
 * 示例 2:
 *   输入: [1,[4,[6]]]
 *   输出: [1,4,6]
 *   解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。
 * @author 刘学松
 * @date 2021-03-23 9:56
 */
public class 扁平化嵌套列表迭代器 {
}

class NestedIterator implements Iterator<Integer> {
    int index = 0;
    List<Integer> list = new ArrayList<>();

    public NestedIterator(List<NestedInteger> nestedList) {
        for(NestedInteger nestedInteger : nestedList) {
            init(nestedInteger);
        }
    }

    public void init(NestedInteger nestedInteger) {
        if (nestedInteger.isInteger()) {
            list.add(nestedInteger.getInteger());
        } else {
            for(NestedInteger x : nestedInteger.getList()) {
                init(x);
            }
        }
    }

    @Override
    public Integer next() {
        return list.get(index++);
    }

    @Override
    public boolean hasNext() {
        return index < list.size();
    }
}

class NestedIterator1 implements Iterator<Integer> {
    Iterator<Integer> iterator;

    public NestedIterator1(List<NestedInteger> nestedList) {
        List<Integer> list = new ArrayList<>();
        for(NestedInteger nestedInteger : nestedList) {
            init(nestedInteger, list);
        }
        this.iterator = list.iterator();
    }

    public void init(NestedInteger nestedInteger, List<Integer> list) {
        if (nestedInteger.isInteger()) {
            list.add(nestedInteger.getInteger());
        } else {
            for(NestedInteger x : nestedInteger.getList()) {
                init(x, list);
            }
        }
    }

    @Override
    public Integer next() {
        return iterator.next();
    }

    @Override
    public boolean hasNext() {
        return iterator.hasNext();
    }
}

interface NestedInteger {

    /**
     * @return true if this NestedInteger holds a single integer, rather than a nested list.
     * Return null if this NestedInteger holds a nested list
     */
    public boolean isInteger();

    /**
     * @return the single integer that this NestedInteger holds, if it holds a single integer
     * Return null if this NestedInteger holds a nested list
     */
    public Integer getInteger();

    /**
     * @return the nested list that this NestedInteger holds, if it holds a nested list
     * Return null if this NestedInteger holds a single integer
     */
    public List<NestedInteger> getList();
}